package com.simple.demo.sort;

/**
 * 快速排序
 */
public class QuickSort {

    public static void main(String[] args) {

        int [] array = new int[]{23,45,12,34,78,90,78,55,27};
        quickSort(array,0,array.length-1);
        for(int data : array){
            System.out.print(data +" ");
        }
    }

    private static void quickSort(int  [] array  ,int lower,int high){
        int i,j , temp,t;
        if(lower >= high){
            return;
        }
        //左边的位置
        i = lower;
        //右边的位置
        j = high;
        //基准原始，也就是最左边的原始
        temp = array[lower];
        while (i < j){

            //从左向右移动
            while(array[j] >= temp && i < j){
                j--;
            }
            //从右向左移动
            while(array[i] <=temp && i < j){
                i++;
            }
            if(i < j ){
                t = array[j];
                array[j] = array[i];
                array[i] = t;
            }
        }
        array[lower] = array[i];
        array[i]= temp;
        //递归左半数组
        quickSort(array,lower,j-1);
        //递归右半数组
        quickSort(array,j+1,high);




    }
}
